package leetcode

// Definition for a Node.
type Node struct {
	Val   int
	Left  *Node
	Right *Node
	Next  *Node
}

// https://leetcode.com/problems/populating-next-right-pointers-in-each-node-ii/
func connect(root *Node) *Node {
	if root == nil {
		return root
	}
	nodes := []*Node{root}
	traversal(nodes)
	return root
}

func traversal(levelNodes []*Node) {
	if len(levelNodes) == 0 {
		return
	}
	nextNodes := make([]*Node, 0)
	var cur *Node = nil
	for _, node := range levelNodes {
		if node.Right != nil {
			nextNodes = append(nextNodes, node.Right)
		}
		if node.Left != nil {
			nextNodes = append(nextNodes, node.Left)
		}
		node.Next = cur
		cur = node
	}
	traversal(nextNodes)
}
